BEZIER CURVES by Storm/Cydonia [taken from Defy #4 by Cydonia] Nobody has ever written any sort of coding lesson in Defy before, so, for issue #4, I decided to do one! Now, I could have written all sorts of wanky stuff for beginners, how to get started coding demos, or some crap like that. But no! Instead, I decided to write a little article on how to draw Bezier Curves. What's a Bezier curve? Well simply enough, it's a curve which is defined by two points marking the start and end of the curve, and one or more "control points", which determine how curvy it is. The curves I'll be talking about here are ones which have two control points as well as the start and end points. These are also known as cubic Bezier curves. What do the control points do? The curve does not pass through the control points. It just curves towards them. For the technically minded, the tangent (or direction of the curve) at the startpoint is equal to a straight line from the startpoint to the first control point; and the tangent at the endpoint is equal to a straight line from the endpoint to the second control point. Have a look at figure 1 to get an idea of this! How do you draw the curve? The basic way to draw the curve involves a cubic parametric equation. If you choked on that phrase - this basically means equations with values squared and values cubed in them! Surely you do not want to figure out such things in a speedy demo. Luckily, there is another method, ˙called "recursive subdivision" which avoids all this ugly maths. Now, when I first taught myself this shit, I never learnt this method because it looked really complicated in the textbook I had. So I did a shitty Bezier routine with heaps of MULs in it - slow!! But, then I got another book, and discovered that this subdivision method is not only much faster, but genuinely easier to understand! So that's what I'll be teaching here. What is recursive subdivision? OK, you have a Bezier curve. Let's say that instead of drawing the curve properly, you just drew a straight line from the startpoint to the endpoint. Now this would be an approximation of the curve - a completely terrible one, but an approximation nevertheless. But what if there was an easy way to split the curve into two separate curves, each with a startpoint and an endpoint (the endpoint of the first would be the same as the startpoint of the second of course) and two control points? See figure 2 for what this would look like. If you could do this, you could split the curve, then approximate each half with a straight line. Slightly better but still crap. But if you split each half in half, and so on a few times, until you had maybe 32 or 64 straight lines, then it would be looking pretty much like a smooth curve! Luckily, there IS an easy way to do this! All it takes is the averaging of some values (so in assembly, just some ADDs and some 1-bit LSRs).. no multiplying or anything slow like that! And here's the maths for it: You have a curve. Let's call the 4 points that make it up P1, P2, P3 and P4. P1 is the startpoint, P4 is the endpoint, and P2 and P3 are the two control points. We want to split this into 2 curves. Well call the point that make up the first curve L1, L2, L3 and L4, and the points that make up the second curve R1, R2, R3 and R4. Remember that L4 and R1 are the same, this is the midpoint of the original curve where the two new curves meet. L1 = P1 These are the start and end R4 = P4 points of the original curve. L2 = average(P1,P2) R3 = average(P3,P4) H = average(P2,P3) H isn't part of either curve, but we'll need it to figure out L3 and R2. L3 = average(L2,H) R2 = average(R3,H) L4 = R1 = average(L3,R2) If you'd like to see what all this looks like, check out figure 3! When I say that one point is the average of two other points, it of course means that you average the X values of those two to get the X value of the new point, and also average the Y values. If you're working in 3D, average the Z values too! In assembly, you can of course average two numbers just by adding them together and shifting the result right one bit. Now what do I do? Alright, you've split the curve in half, split the halves in half, and so on, a few times, and now have maybe 64 little Bezier curves. You're going to pretend that they're not really curves and draw them as straight lines. How you do this is up to you! Surely you have some source handy to draw lines using the blitter? Or, if you use a higher-level language than assembly, you've probably got a Line command to do it for you, so that shouldn't be a problem. Bezier curves are a nice simple way to draw curved objects and spin them around in 2D or 3D space. Think of all the multiplication that's involved in 3D rotation - if you made up a curved object with lots of straight lines, then rotated it in 3D space, you'd have to rotate HEAPS of points. But by making it a Bezier curve, you only have to rotate the 4 points, then you can figure out all the individual lines using, as I said, only ADDs and LSRs. /<-Rad, hey! Making objects. If you want to make up an object out of multiple Bezier curves, you'll probably be wanting them to join together smoothly, so it's one big smoothly curved object, not one visibly made of separate curved sections. Here's how you do it. Let's call the two curves A and B, so the points that make them up are A1, A2, A3, A4, B1, B2, B3 and B4. A4 and B1 are the same point (endpoint of A and startpoint of B). Now, remember how figure 1 showed what the control points did? It should be apparent that if A3, A4 (=B1) and B2 all lie on a straight line, then curves A and B will join together smoothly. See figure 4 for this in action! And that's it! Well, with the info & maths in this article, you should be able to construct complex curved objects out of multiple Bezier curves, and then translate, scale & rotate them in 3D space with minimal calculation. Hopefully there are some coders out there who will benefit from this info!! Thanks Storm! I might even have a go myself! - Ed.